package LeetCode;

/**
 * @Author：DijaH
 * @Date：2023/1/1 9:26 下午
 * @Version：1.0.0
 * @Description： 两个字符串的最长公共子序列
 *
 * 1、使用这两个字符串，一个当列一个当行。建立一个二维表
 * 1、如果str1[0] == str2[0]，那么dp[0][0] = 1
 * 1、在分别判断第一行和第一列
 * 1、str1[0] == str2[j]
 * 1、str1[i] == str2[0]
 * 1、随意在中间的哪个位置，该位置的值取决于这个格子的上面、左侧、左上角的三个格子。所以填充到这个表格的右下角是最后要返回的结果。
 *
 */
public class code1143_LongestCommonSubsequence {

    public static int Subsequence(String s1,String s2){
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }
        char [] str1 = s1.toCharArray();
        char [] str2 = s2.toCharArray();
        int str1Length = str1.length;
        int str2Length = str2.length;
        int [][] dp = new int[str1Length][str2Length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 0; i < str1.length; i++) {
            //第一列
            dp[i][0] = str1[i] == str2[0] ? 1 : 0;
        }
        for(int j =0; j < str2Length ; j++){
            //第一行
            dp[0][j] = str1[0] == str2[j] ? 1 : 0;
        }
        //填充中间的格子
        for (int i = 1; i < str1Length; i++) {
            for(int j = 1; j < str2Length;j++){
                int p1 = dp[i-1][j];
                int p2 = dp[i][j-1];
                int p3 = str1[i-1] == str2[j-1] ? 1+(dp[i-1][j-1]) : 0;
                dp[i][j] = Math.max(p1,Math.max(p2,p3));
            }
        }
        return dp[str1Length-1][str2Length-1];
    }

    public static int way2(String text1,String text2){
        int n = text1.length(), m =  text2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        String str1 = "a1b2b3jh4";
        String str2 = "123nj4";
        System.out.println(Subsequence(str1,str2));
    }
}
